0865. 具有所有最深节点的最小子树【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离。

返回包含原始树中所有 最深节点 的 最小子树。

如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的。

一个节点的 子树 是该节点加上它的所有后代的集合。

---

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的节点为 2，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。

---

提示：

• 树中节点的数量在 [1, 500] 范围内。
• 0 <= Node.val <= 500
• 每个节点的值都是 独一无二 的。

---

注意：本题与力扣 1123. 最深叶节点的最近公共祖先 重复。

2. 🎯 s.1 - DFS

c

struct TreeNode* dfsHelper(struct TreeNode* node, int* depth) {
    if (!node) { *depth = 0; return NULL; }
    int ld, rd;
    struct TreeNode* left = dfsHelper(node->left, &ld);
    struct TreeNode* right = dfsHelper(node->right, &rd);
    if (ld > rd) { *depth = ld + 1; return left; }
    if (rd > ld) { *depth = rd + 1; return right; }
    *depth = ld + 1;
    return node;
}

struct TreeNode* subtreeWithAllDeepest(struct TreeNode* root) {
    int d;
    return dfsHelper(root, &d);
}

js

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var subtreeWithAllDeepest = function (root) {
  const dfs = (node) => {
    if (!node) return [null, 0]
    const [lNode, lDepth] = dfs(node.left)
    const [rNode, rDepth] = dfs(node.right)
    if (lDepth > rDepth) return [lNode, lDepth + 1]
    if (rDepth > lDepth) return [rNode, rDepth + 1]
    return [node, lDepth + 1]
  }
  return dfs(root)[0]
}

py

class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        def dfs(node):
            if not node: return None, 0
            l_node, l_depth = dfs(node.left)
            r_node, r_depth = dfs(node.right)
            if l_depth > r_depth: return l_node, l_depth + 1
            if r_depth > l_depth: return r_node, r_depth + 1
            return node, l_depth + 1
        return dfs(root)[0]

• 时间复杂度：$O(n)$，其中 n 是节点数
• 空间复杂度：$O(n)$，递归栈深度

算法思路：

• DFS 同时返回节点和深度
• 若左子树更深返回左，右子树更深返回右，深度相等返回当前节点

3. 🔗 引用

• 1123. 最深叶节点的最近公共祖先